package com.bow.algorithm.temp;

/**
 * �������һ������d[1..9] = 2 1 5 3 6 4 8 9 7�����Կ���������LIS����Ϊ5�� ����һ��һ�������ҳ�����
 * ���Ƕ���һ������B��Ȼ���� i = 1 to 9 �������������С� ���⣬������һ������Len����¼������㵽������
 * ���ȣ���d[1]����طŵ�B���B[1] = 2������˵��ֻ��1һ������2��ʱ�򣬳���Ϊ1��LIS����Сĩβ��2����ʱLen=1
 * Ȼ�󣬰�d[2]����طŵ�B���B[1] = 1������˵����Ϊ1��LIS����Сĩβ��1��d[1]=2�Ѿ�û���ˣ����������ɡ���ʱLen=1
 * ���ţ�d[3] =  5��d[3]>B[1]��������B[1+1]=B[2]=d[3]=5������˵����Ϊ2��LIS����Сĩβ��5�����������ɡ���ʱ��B[1..2] = 1,5��Len��2 
 * ������d[4] =3�������ü���1,5֮�䣬����1��λ����Ȼ�����ʣ���Ϊ1С��3������Ϊ1��LIS��СĩβӦ����1��������������֪������Ϊ2��LIS��Сĩβ��3 �����ǿ��԰�5��̭������ʱ��B[1..2] = 1, 3��Len = 2 
 * ������d[5] = 6������3���棬��ΪB[2] = 3,��6��3���棬���Ǻ����׿�����֪B[3] = 6, ��ʱB[1..3] = 1, 3, 6�����Ǻ��������ɣ� Len = 3 ���ޡ� 
 * ��6��, d[6]= 4���㿴����3��6֮�䣬�������ǾͿ��԰�6�滻�����õ�B[3] = 4��B[1..3] = 1, 3, 4�� Len��������3 
 * ��7��, d[7] =8�����ܴ󣬱�4���š�����B[4] = 8��Len���4�� 
 * ��8��, d[8] = 9���õ�B[5] = 9���š�Len�������󣬵�5�ˡ� 
 * ���һ��,d[9] = 7������B[3] = 4��B[4] = 8֮�䣬��������֪�������µ�B[4] =7��B[1..5] = 1, 3, 4, 7, 9��Len= 5�� ��������֪����LIS�ĳ���Ϊ5��
 * ע�⡣���1,3,4,7,9����LIS����ֻ�Ǵ洢�Ķ�Ӧ����LIS����Сĩβ���������ĩβ�����ǾͿ���һ��һ���ز������ݡ�
 * ��Ȼ���һ��d[9] =7���½�ȥ������������û��ʲô���壬������������ٳ����������� 8 �� 9����ô�Ϳ��԰�8���µ�d[5], 9���µ�d[6]���ó�LIS�ĳ���Ϊ6��
 * Ȼ��Ӧ�÷���һ��������:
 * ��B�в�������������ģ������ǽ����滻������ҪŲ������Ҳ����˵�����ǿ���ʹ�ö��ֲ��ң���ÿһ�����ֵĲ���ʱ���Ż���O(logN)
 * �����㷨��ʱ�临�ӶȾͽ��͵���O(NlogN)��
 */
public class LongestIncreseSequence2 {
	public static <T extends Comparable<? super T>> int LIS(T[] d) {
		if (d == null) {
			return 0;
		}
		T[] b = (T[]) new Comparable[d.length];
		int left, right, middle, maxLen;
		b[0] = d[0];
		maxLen = 1;
		for (int i = 1; i < d.length; i++) {
			left = 0;
			right = maxLen;
			while (left < right) {
				middle = (left + right) / 2;
				if (b[middle].compareTo(d[i]) < 0) {
					left = middle + 1;
				}
				if (b[middle].compareTo(d[i]) > 0) {
					right = middle - 1;
				}
			}
			b[left] = d[i];
			if (left == maxLen) {
				maxLen++;
			}
		}
		return maxLen;
	}

	public static <T extends Comparable<? super T>> void printpath() {

	}

	public static void main(String[] args) {
		Integer[] d = new Integer[] { 1, -1, 2, -3, 9, 4, -5, 6, -7 };
		int maxlen = LongestIncreseSequence2.LIS(d);
		System.out.println(maxlen);
	}
}
